package com.aug_leo.datastructure.heap;

import java.util.Arrays;

/**
 * 可以扩容的 heap, max 用于指定是大顶堆还是小顶堆
 * <h3>特征</h3>
 * <ul>
 *     <li>
 *         如果从索引 0 开始存在节点数据
 *         <ol>
 *             <li>节点 i 的父节点为 floor((i - 1) / 2)，当 i > 0 时</li>
 *             <li>节点 i 的左子节点为 2 * i + 1，右子节点为 2 * i + 2，当然它们得 < size</li>
 *         </ol>
 *     </li>
 *     <li>
 *         如果从索引 1 开始存在节点数据
 *         <ol>
 *             <li>节点 i 的父节点为 floor((i) / 2)，当 i > 0 时</li>
 *             <li>节点 i 的左子节点为 2 * i，右子节点为 2 * i + 1，当然它们得 < size</li>
 *         </ol>
 *     </li>
 * </ul>
 */
public class Heap {

    /**
     * 堆数组，用于存储堆中的元素
     */
    int[] array;

    /**
     * 堆的当前大小
     */
    int size;

    public int size() {
        return size;
    }

    /**
     * 是否为大顶堆
     */
    boolean max;

    /**
     * 构造函数，初始化堆的实例
     *
     * @param capacity 堆的最大容量，即能够包含的元素数量上限
     * @param max      指示创建的是最大堆还是最小堆的标志，true为最大堆，false为最小堆
     */
    public Heap(int capacity, boolean max) {
        this.array = new int[capacity];
        this.max = max;
    }

    /**
     * 获取堆顶元素
     *
     * @return 堆顶元素
     */
    public int peek() {
        if (isEmpty()) {
            throw new IllegalArgumentException("堆为空，不能获取堆顶元素");
        }
        return array[0];
    }


    /**
     * 删除堆顶元素
     *
     * @return 堆顶元素
     */
    public int poll() {
        if (isEmpty()) {
            throw new IllegalArgumentException("堆为空，不能删除元素");
        }
        int top = array[0];
        swap(0, size - 1);
        size--;
        down(0);
        return top;
    }

    /**
     * 删除指定索引处元素
     *
     * @param index 索引
     * @return 被删除元素
     */
    public int poll(int index) {
        if (isEmpty()) {
            throw new IllegalArgumentException("堆为空，不能删除元素");
        }
        if (index >= size) {
            throw new IllegalArgumentException("索引超出范围");
        }
        int deleted = array[index];
        // 如果要删除的是最后一个元素，则无需交换
        if (index != size - 1) {
            swap(index, size - 1);
        }
        size--;
        down(index);
        return deleted;
    }

    /**
     * 替换堆顶元素
     *
     * @param replaced 新元素
     */
    public void replace(int replaced) {
        if (isEmpty()) {
            throw new IllegalArgumentException("堆为空，不能替换堆顶元素");
        }
        array[0] = replaced;
        down(0);
    }

    /**
     * 堆的尾部添加元素
     *
     * @param offered 新元素
     * @return 是否添加成功
     */
    public boolean offer(int offered) {
        if (isFull()) {
            // 扩容
            grow();
        }
        up(offered);
        size++;
        return true;
    }

    /**
     * 扩容
     */
    private void grow() {
        int capacity = size + (size >> 1);
        int[] newArray = new int[capacity];
        System.arraycopy(array, 0,
                newArray, 0, array.length);
        array = newArray;
    }

    public Heap(int[] array) {
        this.array = array;
        this.size = array.length;
        heapify();
    }

    /**
     * Floyd建堆算法
     * <ol>
     *     <li>找到最后一个非叶子节点</li>
     *     <li>从后向前，堆每个节点执行下潜</li>
     * </ol>
     */
    private void heapify() {
        // 如何找到最后这个非叶子节点    size / 2 - 1
        for (int i = size / 2 - 1; i >= 0; i--) {
            down(i);
        }
    }


    /**
     * 将元素上移以维持堆的性质
     * 当插入一个新元素或增加一个元素时，需要调用此方法将元素上移到正确的位置
     *
     * @param offered 要上移的元素值
     */
    private void up(int offered) {
        int child = size;
        while (child > 0) {
            int patent = (child - 1) / 2;
            boolean cmp = max ? offered > array[patent] : offered < array[patent];
            if (cmp) { // 如果需要交换
                // 将父节点的值赋给子节点
                array[child] = array[patent];
            } else {
                break; // 如果不需要交换，跳出循环
            }
            child = patent;
        }
        array[child] = offered;

    }


    /**
     * 将元素下移以维持堆的性质
     * 当删除堆顶元素或减少一个元素时，需要调用此方法将元素下移到正确的位置
     *
     * @param parent 要下移的元素的索引
     */
    private void down(int parent) {
        int left = 2 * parent + 1;
        int right = left + 1;
        int maxOrMin = parent;
        // 比较左右子节点，找出最大或最小
        if (left < size && (max ? array[left] > array[maxOrMin] : array[left] < array[maxOrMin])) {
            maxOrMin = left;
        }

        if (right < size && (max ? array[right] > array[maxOrMin] : array[right] < array[maxOrMin])) {
            maxOrMin = right;
        }

        // 如果最大或最小的不是父节点本身
        if (maxOrMin != parent) {
            swap(maxOrMin, parent);
            down(maxOrMin);
        }
    }

    /**
     * 交换两个索引处的元素
     *
     * @param i 第一个索引
     * @param j 第二个索引
     */
    private void swap(int i, int j) {
        int temp = this.array[i];
        this.array[i] = this.array[j];
        this.array[j] = temp;
    }

    /**
     * 检查堆是否为空
     *
     * @return 空返回 true, 否则返回 false
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 检查堆是否已满
     *
     * @return 满返回 true, 否则返回 false
     */
    public boolean isFull() {
        return size == array.length;
    }

    /*
              100
           /      \
          10      99
         / \      / \
        5   6    98 97
       /\   /\   /
      1 2  3  4 96

              100
           /      \
          96      99
         / \      / \
        10   6   98 97
       /\   /\
      1 2  3  4
     */
    public static void main(String[] args) {
        Heap heap = new Heap(5, true); //100,10,99,5,6,98,97,1,2,3,4,96
        heap.offer(100);
        heap.offer(10);
        heap.offer(99);
        heap.offer(5);
        heap.offer(6);
        heap.offer(98);
        heap.offer(97);
        heap.offer(1);
        heap.offer(2);
        heap.offer(3);
        heap.offer(4);
        heap.offer(96);
        System.out.println(Arrays.toString(heap.array));
        System.out.println(heap.size);
        System.out.println(heap.poll(3));
        System.out.println(Arrays.toString(heap.array));
        System.out.println(heap.size);
    }
}
